{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Palindrome Partitioning IV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: checkPartitioning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分割回文串 IV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> ，如果可以将它分割成三个 <strong>非空</strong> 回文子字符串，那么返回 <code>true</code> ，否则返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>当一个字符串正着读和反着读是一模一样的，就称其为 <strong>回文字符串</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"abcbdd\"\n",
    "<b>输出：</b>true\n",
    "<strong>解释：</strong>\"abcbdd\" = \"a\" + \"bcb\" + \"dd\"，三个子字符串都是回文的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"bcbddxy\"\n",
    "<b>输出：</b>false\n",
    "<strong>解释：</strong>s 没办法被分割成 3 个回文子字符串。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 <= s.length <= 2000</code></li>\n",
    "\t<li><code>s</code>​​​​​​ 只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [palindrome-partitioning-iv](https://leetcode.cn/problems/palindrome-partitioning-iv/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [palindrome-partitioning-iv](https://leetcode.cn/problems/palindrome-partitioning-iv/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abcbdd\"', '\"bcbddxy\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def checkPartitioning(self,s):\n",
    "        a,b=[0],[len(s)-1]\n",
    "        for i in range(1,len(s)-1):\n",
    "            if s[i]==s[0]:\n",
    "                if s[:i+1]==s[:i+1][::-1]:\n",
    "                    a.append(i)\n",
    "            if s[i] == s[-1]:\n",
    "                if s[i:] == s[i:][::-1]:\n",
    "                    b.append(i)\n",
    "        for i in range(len(a)):\n",
    "            for j in range(len(b)):\n",
    "                if a[i]<b[j]-1:\n",
    "                    if s[a[i]+1]==s[b[j]-1]:\n",
    "                        if s[a[i]+1:b[j]]==s[a[i]+1:b[j]][::-1]:\n",
    "                            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i + 1, len(s)):\n",
    "                if self.check(s[0:i]) and self.check(s[i:j]) and self.check(s[j:]):\n",
    "                    return True\n",
    "        return False\n",
    "    \n",
    "    def check(self, s):\n",
    "        if len(s) == 0:\n",
    "            return False\n",
    "        if s == s[::-1]:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def checkPartitioning(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        a,b = [0],[len(s)-1]\n",
    "        for i in range(1,len(s)-1):\n",
    "            if s[i] == s[0]:\n",
    "                if s[:i+1] == s[:i+1][::-1]:\n",
    "                    a.append(i)\n",
    "            if s[i] == s[-1]:\n",
    "                if s[i:] == s[i:][::-1]:\n",
    "                    b.append(i)\n",
    "        for i in range(len(a)):\n",
    "            for j in range(len(b)):\n",
    "                if a[i] < b[j] - 1:\n",
    "                    if s[a[i]+1] == s[b[j]-1]:\n",
    "                        if s[a[i]+1:b[j]] == s[a[i]+1:b[j]][::-1]:\n",
    "                            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def checkPartitioning(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        a,b = [0],[len(s)-1]\n",
    "        for i in range(1,len(s)-1):\n",
    "            if s[i] == s[0]:\n",
    "                if s[:i+1] == s[:i+1][::-1]:\n",
    "                    a.append(i)\n",
    "            if s[i] == s[-1]:\n",
    "                if s[i:] == s[i:][::-1]:\n",
    "                    b.append(i)\n",
    "        for i in range(len(a)):\n",
    "            for j in range(len(b)):\n",
    "                if a[i] < b[j] - 1:\n",
    "                    if s[a[i]+1] == s[b[j]-1]:\n",
    "                        if s[a[i]+1:b[j]] == s[a[i]+1:b[j]][::-1]:\n",
    "                            return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def checkPartitioning(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        a,b = [0],[len(s)-1]\n",
    "        for i in range(1,len(s)-1):\n",
    "            if s[i] == s[0]:\n",
    "                if s[:i+1] == s[:i+1][::-1]:\n",
    "                    a.append(i)\n",
    "            if s[i] == s[-1]:\n",
    "                if s[i:] == s[i:][::-1]:\n",
    "                    b.append(i)\n",
    "        for i in range(len(a)):\n",
    "            for j in range(len(b)):\n",
    "                if a[i] < b[j] - 1:\n",
    "                    if s[a[i]+1] == s[b[j]-1]:\n",
    "                        if s[a[i]+1:b[j]] == s[a[i]+1:b[j]][::-1]:\n",
    "                            return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "\n",
    "        def isPali(s):         \n",
    "            left,right = 0,len(s)-1\n",
    "            while left<right:\n",
    "                if s[left] !=s[right]:\n",
    "                    return False\n",
    "                left+=1\n",
    "                right-=1\n",
    "            return True\n",
    "\n",
    "        pre = []\n",
    "        suf = []\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if s[0:i+1]==s[0:i+1][::-1]:\n",
    "                pre.append(i)\n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            if s[i:]==s[i:][::-1]:\n",
    "                suf.append(i)\n",
    "        \n",
    "        for i in pre:\n",
    "            for j in suf:\n",
    "                if i+1>=j:\n",
    "                    continue\n",
    "                if s[i+1:j]==s[i+1:j][::-1]:\n",
    "                    return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def checkPartitioning(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        a,b = [0],[len(s)-1]\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == s[0]:\n",
    "                if s[:i+1] == s[:i+1][::-1]:\n",
    "                    a.append(i)\n",
    "            if s[i] == s[-1]:\n",
    "                if s[i:] == s[i:][::-1]:\n",
    "                    b.append(i)\n",
    "        for i in range(len(a)):\n",
    "            for j in range(len(b)):\n",
    "                if a[i] < b[j] - 1:\n",
    "                    if s[a[i]+1] == s[b[j]-1]:\n",
    "                        if s[a[i]+1:b[j]] == s[a[i]+1:b[j]][::-1]:\n",
    "                            return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "\n",
    "        def isPali(s):         \n",
    "            left,right = 0,len(s)-1\n",
    "            while left<right:\n",
    "                if s[left] !=s[right]:\n",
    "                    return False\n",
    "                left+=1\n",
    "                right-=1\n",
    "            return True\n",
    "\n",
    "        pre = []\n",
    "        suf = []\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if s[0:i+1]==s[0:i+1][::-1]:\n",
    "                pre.append(i)\n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            if s[i:]==s[i:][::-1]:\n",
    "                suf.append(i)\n",
    "        \n",
    "        for i in pre:\n",
    "            for j in suf:\n",
    "                if i+1>=j:\n",
    "                    continue\n",
    "                if s[i+1:j]==s[i+1:j][::-1]:\n",
    "                    return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Manacher:\n",
    "    def __init__(self, string=''):\n",
    "        self.string = string\n",
    "\n",
    "    def add_char(self):\n",
    "        add_string = '^'\n",
    "        for char in self.string:\n",
    "            add_string += '@' + char\n",
    "        add_string += '@*'\n",
    "        return add_string\n",
    "    \n",
    "    def get_p(self): \n",
    "        self.add_string = self.add_char()\n",
    "        self.P = [0] * len(self.add_string)\n",
    "        R, mid = 0, 0\n",
    "        for i in range(1, len(self.add_string)-1):\n",
    "            self.P[i] = min(self.P[mid*2-i], R-i) if R > i else 0\n",
    "            while self.add_string[i+1+self.P[i]] == self.add_string[i-1-self.P[i]]:\n",
    "                self.P[i] +=1\n",
    "            if i + self.P[i] > R:\n",
    "                R = i + self.P[i]\n",
    "                mid = i\n",
    "        return self.P\n",
    "    \n",
    "    def check_partition_s(self, l, r): # 判断在串S的区间[l,r]的子串是否为回文串。\n",
    "        l, r = l * 2 + 2, r * 2 + 2\n",
    "        mid = (l + r) // 2\n",
    "        return self.P[mid] > r - mid\n",
    "    \n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        manacher = Manacher(s)\n",
    "        manacher.get_p()\n",
    "        n = len(s)\n",
    "        pre, suf = [], []\n",
    "        pre_vis = [0] * n \n",
    "        suf_vis = [0] * n\n",
    "        for i in range(0, n):\n",
    "            if manacher.check_partition_s(0, n-1-i):\n",
    "                pre.append(n-i-1)\n",
    "                pre_vis[n-i-1] = 1\n",
    "            if manacher.check_partition_s(i, n-1):\n",
    "                suf.append(i)\n",
    "                suf_vis[i] = 1\n",
    "\n",
    "        suf_n, cnt = len(suf), 0\n",
    "        for i in range(n):\n",
    "            if pre_vis[i]:\n",
    "                while cnt < suf_n and suf[cnt] < i + 2:\n",
    "                    cnt +=1\n",
    "                if cnt < suf_n and manacher.check_partition_s(i+1, suf[cnt]-1):\n",
    "                    return True\n",
    "        \n",
    "        # print(pre, suf, pre_vis, suf_vis)\n",
    "        pre_n, cnt = len(pre), 0\n",
    "        for i in range(n-1, 0, -1):\n",
    "            if suf_vis[i]:\n",
    "                while cnt < pre_n and pre[cnt] + 2 > i:\n",
    "                    cnt +=1\n",
    "                if cnt < pre_n and manacher.check_partition_s(pre[cnt]+1, i-1):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "\n",
    "        def isPali(s):         \n",
    "            left,right = 0,len(s)-1\n",
    "            while left<right:\n",
    "                if s[left] !=s[right]:\n",
    "                    return False\n",
    "                left+=1\n",
    "                right-=1\n",
    "            return True\n",
    "\n",
    "        pre = []\n",
    "        suf = []\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if s[0:i+1]==s[0:i+1][::-1]:\n",
    "                pre.append(i)\n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            if s[i:]==s[i:][::-1]:\n",
    "                suf.append(i)\n",
    "        \n",
    "        for i in pre:\n",
    "            for j in suf:\n",
    "                if i+1>=j:\n",
    "                    continue\n",
    "                if s[i+1:j]==s[i+1:j][::-1]:\n",
    "                    return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "\n",
    "        def isPali(s):         \n",
    "            left,right = 0,len(s)-1\n",
    "            while left<right:\n",
    "                if s[left] !=s[right]:\n",
    "                    return False\n",
    "                left+=1\n",
    "                right-=1\n",
    "            return True\n",
    "\n",
    "        pre = []\n",
    "        suf = []\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if s[0:i+1]==s[0:i+1][::-1]:\n",
    "                pre.append(i)\n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            if s[i:]==s[i:][::-1]:\n",
    "                suf.append(i)\n",
    "        \n",
    "        for i in pre:\n",
    "            for j in suf:\n",
    "                if i+1>=j:\n",
    "                    continue\n",
    "                if s[i+1:j]==s[i+1:j][::-1]:\n",
    "                    return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Manacher:\n",
    "    def __init__(self, string=''):\n",
    "        self.string = string\n",
    "\n",
    "    def add_char(self):\n",
    "        \"\"\"\n",
    "        对字符串预处理填充'#'，使得字符串长度强行满足奇数对称。\n",
    "        同时头尾插入一对不匹配字符，添加P数组计算的边界情况。\n",
    "        \"\"\"\n",
    "        add_string = '^'\n",
    "        for char in self.string:\n",
    "            add_string += '@' + char\n",
    "        add_string += '@*'\n",
    "        return add_string\n",
    "    \n",
    "    def get_p(self): # Manacher算法核心，利用对称性中心扩展O(n)计算P数组\n",
    "        self.add_string = self.add_char()\n",
    "        self.P = [0] * len(self.add_string)\n",
    "        R, mid = 0, 0\n",
    "        for i in range(1, len(self.add_string)-1):\n",
    "            self.P[i] = min(self.P[mid*2-i], R-i) if R > i else 0\n",
    "            while self.add_string[i+1+self.P[i]] == self.add_string[i-1-self.P[i]]:\n",
    "                self.P[i] +=1\n",
    "            if i + self.P[i] > R:\n",
    "                R = i + self.P[i]\n",
    "                mid = i    \n",
    "        return self.P\n",
    "    \n",
    "    def max_palindrome(self):\n",
    "        \"\"\"\n",
    "        利用manacher已计算好的P数组，输出最长的回文子串。可以直接解决 Leetcode 5. 最长回文子串\n",
    "        \"\"\"\n",
    "        self.get_p()\n",
    "        max_len, max_index = 0, 0\n",
    "        for index, value in enumerate(self.P):\n",
    "            if value > max_len:\n",
    "                max_len, max_index = value, index\n",
    "        start_index = (max_index - max_len) // 2\n",
    "        return self.string[start_index: start_index+max_len]\n",
    "\n",
    "    def check_partition_s(self, l, r): # 判断在串S的区间[l,r]的子串是否为回文串。\n",
    "        l, r = l * 2 + 2, r * 2 + 2\n",
    "        mid = (l + r) // 2\n",
    "        return self.P[mid] > r - mid\n",
    "        \n",
    "    def check_partition_p(self, l, r): # 判断在数组P的区间[l,r]内是否为回文串。\n",
    "        mid = (l + r) // 2\n",
    "        return self.P[mid] > r - mid\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        manacher = Manacher(s)\n",
    "        manacher.get_p()\n",
    "        n = len(s)\n",
    "        pre, suf = [], []\n",
    "        pre_vis, suf_vis = [0] * n, [0] * n\n",
    "        for i in range(0, n):\n",
    "            if manacher.check_partition_s(0, n-1-i):\n",
    "                pre.append(n-i-1)\n",
    "                pre_vis[n-i-1] = 1\n",
    "            if manacher.check_partition_s(i, n-1):\n",
    "                suf.append(i)\n",
    "                suf_vis[i] = 1\n",
    "\n",
    "        suf_n, cnt = len(suf), 0\n",
    "        for i in range(n):\n",
    "            if pre_vis[i]:\n",
    "                while cnt < suf_n and suf[cnt] < i + 2:\n",
    "                    cnt +=1\n",
    "                if cnt < suf_n and manacher.check_partition_s(i+1, suf[cnt]-1):\n",
    "                    return True\n",
    "        pre_n, cnt = len(pre), 0\n",
    "        for i in range(n-1, 0, -1):\n",
    "            if suf_vis[i]:\n",
    "                while cnt < pre_n and pre[cnt] + 2 > i:\n",
    "                    cnt +=1\n",
    "                if cnt < pre_n and manacher.check_partition_s(pre[cnt]+1, i-1):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dfs(i, c):\n",
    "            if c == 2:\n",
    "                return i<=n-1 and s[i:] == s[i:][::-1]\n",
    "            for j in range(i, n - 1):\n",
    "                if s[i:j + 1] == s[i:j + 1][::-1]:\n",
    "                    if dfs(j + 1, c + 1):\n",
    "                        return True\n",
    "            return False\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        \n",
    "        @cache\n",
    "        def can(s, cnt) -> bool:\n",
    "            # print(\"--1\", s)\n",
    "            if cnt==3:\n",
    "                return True if len(s) == 0 else False\n",
    "            \n",
    "            for i in range(1,len(s)+1):\n",
    "                t = s[0:i]\n",
    "                # print(\"--\", t)\n",
    "                if t == t[::-1] and can(s[i:], cnt+1):\n",
    "                    # print(t)\n",
    "                    return True\n",
    "            return False\n",
    "        return can(s, 0)\n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        \n",
    "        @cache\n",
    "        def can(s, cnt) -> bool:\n",
    "            # print(\"--1\", s)\n",
    "            if cnt==3:\n",
    "                return True if len(s) == 0 else False\n",
    "            \n",
    "            for i in range(len(s)):\n",
    "                t = s[0:i+1]\n",
    "                # print(\"--\", t)\n",
    "                if t == t[::-1] and can(s[i+1:], cnt+1):\n",
    "                    # print(t)\n",
    "                    return True\n",
    "            return False\n",
    "        return can(s, 0)\n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        dp = [[True]*n for _ in range(n)]\n",
    "        for end in range(n):\n",
    "            for start in range(end):\n",
    "                if end == start+1:\n",
    "                    dp[start][end] = s[start] == s[end]\n",
    "                else:\n",
    "                    dp[start][end] = s[start] == s[end] and dp[start+1][end-1]\n",
    "        for subxi in range(n):\n",
    "            for prexi in range(subxi-1):\n",
    "                if dp[0][prexi] and dp[prexi+1][subxi-1] and dp[subxi][n-1]:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        if n <= 2: return False\n",
    "        dp = [[False] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = True\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if i + 1 < n:\n",
    "                dp[i][i+1] = s[i] == s[i+1]\n",
    "            for j in range(i+2, n):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i+1][j-1]\n",
    "                elif s[i] != s[j]:\n",
    "                    dp[i][j] = False\n",
    "        for i in range(1, n-1):\n",
    "            for j in range(i+1, n):\n",
    "                if dp[0][i-1] and dp[i][j-1] and dp[j][n-1]:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        dp = [[None] * n for _ in range(n)]\n",
    "\n",
    "        for j in range (0, n):\n",
    "            for i in range(j, -1, -1):\n",
    "                if s[i] ==s[j]:\n",
    "                    if j < i + 2:\n",
    "                        dp[i][j] = True\n",
    "                    else:\n",
    "                         dp[i][j] = dp[i+1] [j-1]\n",
    "                else:\n",
    "                    dp [i][j] = False  \n",
    "\n",
    "        for i in range(1, n-1):\n",
    "            for j in range(i, n - 1):\n",
    "                if dp [0][i-1] and dp [i][j] and dp [j + 1] [n - 1]:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        ispal = [[True] * n for _ in range(n)]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            for j in range(i+1, n):\n",
    "                ispal[i][j] = ispal[i+1][j-1] and s[i] == s[j]\n",
    "\n",
    "        for i in range(1, n-1):\n",
    "            for j in range(i, n-1):\n",
    "                if ispal[0][i-1] and ispal[i][j] and ispal[j+1][n-1]:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "\n",
    "        # dp[i,j]\n",
    "\n",
    "        n = len(s)\n",
    "\n",
    "        dp = [[True] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                if dp[i + 1][j - 1] and s[i] == s[j]:\n",
    "                    dp[i][j] = True\n",
    "                else:\n",
    "                    dp[i][j] = False\n",
    "\n",
    "        for i in range(len(s) - 2):\n",
    "            # [0, i]\n",
    "            if not dp[0][i]:\n",
    "                continue \n",
    "            for j in range(i + 1, len(s) - 1):\n",
    "                # [i + 1, j]\n",
    "\n",
    "                # [j + 1, n - 1] \n",
    "\n",
    "                if dp[i + 1][j] and dp[j + 1][len(s) - 1]:\n",
    "                    return True\n",
    "\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "\n",
    "        f = [[True] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                f[i][j] = (s[i] == s[j]) and f[i + 1][j - 1]\n",
    "        \n",
    "        for i in range(n):\n",
    "            if f[0][i]:\n",
    "                for j in range(i + 1, n - 1):\n",
    "                    if f[i + 1][j] and f[j + 1][-1]:\n",
    "                        return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        n=len(s)\n",
    "        if n<3:return False\n",
    "        dp=[[False]*n for _ in range(n)]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(i,n):\n",
    "                dp[i][j]= s[i]==s[j] and (j-i<=2 or dp[i+1][j-1])\n",
    "        for i in range(0,n-2):\n",
    "            for j in range(i+1,n-1):\n",
    "                if dp[0][i] and dp[i+1][j] and dp[j+1][n-1]:\n",
    "                    return True \n",
    "        return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n):\n",
    "            dp[i][i] = 1\n",
    "            if s[i] == s[i-1]:\n",
    "                dp[i-1][i] = 1\n",
    "        for j in range(2, n):\n",
    "            for i in range(n-j):\n",
    "                if s[i] == s[i+j] and dp[i+1][i+j-1] == 1:\n",
    "                    dp[i][i+j] = 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n-1):\n",
    "                if dp[0][i] == 1 and dp[i+1][j] == 1 and dp[j+1][n-1]:\n",
    "                    return True\n",
    "        return False\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        \n",
    "        # 建立一个二维dp数组用来存放 s[i:j] 是否为回文串\n",
    "        n = len(s)\n",
    "        dp = [[True] * n for _ in range(n)]\n",
    "        \n",
    "        # 计算dp\n",
    "        for l in range(2, n + 1): # 从长度为2开始，因为长度为1必为回文串\n",
    "            for i in range(0, n + 1 - l):\n",
    "                dp[i][i + l - 1] = dp[i + 1][i + l - 2] and s[i] == s[i + l - 1]\n",
    "        \n",
    "        # 遍历两个隔板i，j的位置，判断三个子串是否都是回文串 [0, i-1], [i, j-1], [j, n-1]\n",
    "        for i in range(1, n):\n",
    "            for j in range(i + 1, n):\n",
    "                if dp[0][i - 1] and dp[i][j - 1] and dp[j][n - 1]:\n",
    "                    return True\n",
    "                \n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        f = [[False] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            f[i][i] = True\n",
    "        \n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i, n):\n",
    "                if s[i] == s[j]:\n",
    "                    if i + 1 >= j:\n",
    "                        f[i][j] = True\n",
    "                    else:\n",
    "                        f[i][j] = f[i + 1][j - 1]\n",
    "        \n",
    "        for i in range(1, n - 1):\n",
    "            for j in range(i, n - 1):\n",
    "                if f[0][i - 1] and f[i][j] and f[j + 1][n - 1]:\n",
    "                    return True\n",
    "        # print(f[0][0], f[1][3], f[4][5])\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        dp = [[None] * n for _ in range(n)]\n",
    "\n",
    "        for j in range(0, n):\n",
    "            for i in range(j, -1, -1):\n",
    "                if s[i] == s[j]:\n",
    "                    if j < i + 2:\n",
    "                        dp[i][j] = True\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i + 1][j - 1]\n",
    "                else:\n",
    "                    dp[i][j] = False\n",
    "\n",
    "        for i in range(1, n - 1):\n",
    "            for j in range(i, n - 1):\n",
    "                if dp[0][i - 1] and dp[i][j] and dp[j + 1][n - 1]:\n",
    "                    return True\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        if not s: return False\n",
    "        n = len(s)\n",
    "        if n < 3: return False\n",
    "        #dp[i][j]表示s[i:j+1]是否是回文\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            dp[i][i] = 1\n",
    "            if i + 1 < n:\n",
    "                dp[i][i+1] = s[i] == s[i+1]\n",
    "            for j in range(i+2, n):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i+1][j-1]\n",
    "        for i in range(1, n-1):\n",
    "            for j in range(i+1, n):\n",
    "                if dp[0][i-1] and dp[i][j-1] and dp[j][n-1]:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        f = [[False] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            f[i][i] = True\n",
    "        \n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i, n):\n",
    "                if s[i] == s[j]:\n",
    "                    if i + 1 >= j - 1:\n",
    "                        f[i][j] = True\n",
    "                    else:\n",
    "                        f[i][j] = f[i + 1][j - 1]\n",
    "        \n",
    "        for i in range(1, n - 1):\n",
    "            for j in range(i, n - 1):\n",
    "                if f[0][i - 1] and f[i][j] and f[j + 1][n - 1]:\n",
    "                    return True\n",
    "        # print(f[0][0], f[1][3], f[4][5])\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        f = [[False] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            f[i][i] = True\n",
    "        for i in range(1, n):\n",
    "            if s[i - 1] == s[i]:\n",
    "                f[i - 1][i] = True\n",
    "        for l in range(3, n - 1):\n",
    "            for i in range(l - 1, n):\n",
    "                f[i - l + 1][i] = f[i - l + 2][i - 1] and s[i - l + 1] == s[i]\n",
    "                # print(l, i - l + 1, i, f[i - l + 1][i])\n",
    "        for i in range(n - 2):\n",
    "            for j in range(i + 1, n - 1):\n",
    "                \n",
    "                if f[0][i] and f[i + 1][j] and f[j + 1][n - 1]:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        ispal = [[True] * n for _ in range(n)]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            for j in range(i+1, n):\n",
    "                ispal[i][j] = ispal[i+1][j-1] and s[i] == s[j]\n",
    "\n",
    "        k = 3\n",
    "        dp = [[False] * (k+1) for _ in range(n+1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(n):\n",
    "            for kk in range(1, k+1):\n",
    "                dp[i+1][kk] = any(dp[j][kk-1] and ispal[j][i] for j in range(i+1))\n",
    "        return dp[n][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        iscycle = [[False] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            iscycle[i][i] = True\n",
    "            if i != n-1 and s[i] == s[i+1]:\n",
    "                iscycle[i][i+1] = True\n",
    "        for l in range(3, n+1):\n",
    "            for i in range(n):\n",
    "                if i + l - 1 >= n:\n",
    "                    break\n",
    "                iscycle[i][i+l-1] = iscycle[i+1][i+l-2] and s[i] == s[i+l-1]\n",
    "        \n",
    "        # for row in iscycle:\n",
    "        #     print(row)\n",
    "\n",
    "        for i in range(1, n-1):\n",
    "            for j in range(i, n-1):\n",
    "                if iscycle[0][i-1] and iscycle[i][j] and iscycle[j+1][n-1]:\n",
    "                    return True\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        f = [[False] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            f[i][i] = True\n",
    "            for j in range(i):\n",
    "                if s[i] == s[j]: \n",
    "                    if i == j + 1: f[j][i] = True\n",
    "                    else: f[j][i] = f[j + 1][i - 1]\n",
    "                else: f[j][i] = False\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if j < n - 1 and f[0][i] and f[i + 1][j] and f[j + 1][n - 1]: return True\n",
    "        # print(f)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        # 使用动态规划计算 s 中每一对字符之间的子字符串是否是回文\n",
    "        dp = [[False] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i, n):\n",
    "                if s[i] == s[j] and (j - i <= 1 or dp[i+1][j-1]):\n",
    "                    dp[i][j] = True\n",
    "        \n",
    "        # 遍历所有可能的分割点\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if dp[0][i] and dp[i+1][j-1] and dp[j][n-1]:\n",
    "                    return True\n",
    "                    \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        isPrime = [[False] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            isPrime[i][i] = True\n",
    "            for j in range(i + 1, n):\n",
    "                isPrime[i][j] = s[i] == s[j] and (j - i <= 1 or isPrime[i+1][j-1])\n",
    "        return any(isPrime[0][i-1] and isPrime[i][j] and isPrime[j+1][n-1] for i in range(1, n-1) for j in range(i, n-1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        dp = [[False]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = True\n",
    "            if i+1 < n:\n",
    "                dp[i][i+1] = s[i]==s[i+1]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i+2, n):\n",
    "                if 11-i == j-11:\n",
    "                    i == i\n",
    "                dp[i][j] = dp[i+1][j-1] and (s[i]==s[j])\n",
    "\n",
    "        for i in range(n-2):\n",
    "            if dp[0][i]:\n",
    "                for j in range(i+1, n-1):\n",
    "                    if dp[i+1][j] and dp[j+1][-1]:\n",
    "                        return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        dp = [[True for __ in range(len(s))] for __ in range(len(s))]\n",
    "\n",
    "        for i in range(len(s)-1, -1, -1):\n",
    "            for j in range(i+1, len(s)):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i+1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] =False\n",
    "\n",
    "        for i in range(1, len(s)):\n",
    "            for j in range(i, len(s) -1):\n",
    "                if dp[0][i-1] and dp[i][j] and dp[j+1][-1]:\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        dp = [[False] * n for _ in range(n)]\n",
    "        for k in range(1, n):\n",
    "            for i in range(n - k + 1):\n",
    "                j = i + k - 1\n",
    "                dp[i][j] = s[i] == s[j] and (k <= 2 or dp[i + 1][j - 1])\n",
    "        for i in range(1, n):\n",
    "            for j in range(i + 1, n):\n",
    "                if dp[0][i - 1] and dp[i][j - 1] and dp[j][n - 1]:\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "\n",
    "        dp = [[True for _ in range(len(s))] for _ in range(len(s))]\n",
    "\n",
    "        for i in range(len(s)-1, -1, -1):\n",
    "            for j in range(i+1, len(s)):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i+1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = False\n",
    "\n",
    "        flag = False\n",
    "\n",
    "        # print(dp)\n",
    "\n",
    "        for i in range(1, len(s)):\n",
    "            for j in range(i, len(s)-1):\n",
    "\n",
    "                if dp[0][i-1] and dp[i][j] and dp[j+1][-1]:\n",
    "                    flag = True\n",
    "\n",
    "        return flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        dp = [[False] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = True\n",
    "        for i in range(n - 1):\n",
    "            dp[i][i + 1] = s[i] == s[i + 1]\n",
    "        for length in range(3, n + 1):\n",
    "            for i in range(n - length + 1):\n",
    "                j = i + length - 1\n",
    "                dp[i][j] = dp[i + 1][j - 1] and s[i] == s[j]\n",
    "        for i in range(n - 2):\n",
    "            for j in range(i + 1, n - 1):\n",
    "                if dp[0][i] and dp[i + 1][j] and dp[j + 1][n - 1]:\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        g = [[True for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i+1, n):\n",
    "                g[i][j] = (s[i] == s[j]) and g[i+1][j-1]\n",
    "        \n",
    "        for i in range(n):\n",
    "            if g[0][i]:\n",
    "                for j in range(i+1, n - 1):\n",
    "                    if g[i+1][j] and g[j+1][n-1]:\n",
    "                        return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "\n",
    "\"\"\"\n",
    "------------------------------------------------\n",
    "@Author : Jianhui Luo\n",
    "@FileName : 1745. 分割回文串 IV.py\n",
    "@Time : Created in 10:41 2023/09/08\n",
    "@Motto : 天行健，君子当自强不息。\n",
    "@Description :\n",
    "给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。\n",
    "\n",
    "当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。\n",
    "--------------------------------------------------\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def is_pari(self, s):\n",
    "        n = len(s)\n",
    "        pari_dp = [[False for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        for right in range(n):\n",
    "            for left in range(right + 1):  # 表示一个字符也要取\n",
    "                if s[left] == s[right] and (right - left <= 2 or pari_dp[left + 1][right - 1]):\n",
    "                    pari_dp[left][right] = True\n",
    "\n",
    "        return pari_dp\n",
    "\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        pari_dp = self.is_pari(s)\n",
    "\n",
    "        # 然后将字符串氛围begin，mid，n-1三个区域\n",
    "        n = len(s)\n",
    "        for begin in range(0,n-1):\n",
    "            for mid in range(begin, n-1):\n",
    "                if pari_dp[0][begin] and pari_dp[begin+1][mid] and pari_dp[mid+1][n-1]:\n",
    "                    return True\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        # dp[i][j] i~j之间字符串是否回文\n",
    "        dp = [[True for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        for j in range(n):\n",
    "            for i in range(j):\n",
    "                dp[i][j] = dp[i+1][j-1] and (s[i] == s[j])\n",
    "        \n",
    "        # i,j 表示中间段的起始位置，1 <= i <= j <= n-2\n",
    "        for i in range(1, n-1):\n",
    "            for j in range(i, n-1):\n",
    "                # 三段都是回文，则返回True\n",
    "                if dp[0][i-1] and dp[i][j] and dp[j+1][n-1]:\n",
    "                    return True\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "\n",
    "        n = len(s)\n",
    "\n",
    "        dp = [[False for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            dp[i][i] = True \n",
    "\n",
    "        for i in range(n-2, -1, -1):\n",
    "            for j in range(i+1, n):\n",
    "                dp[i][j] = True if s[i] == s[j] and (j-i<2 or dp[i+1][j-1]) else False \n",
    "\n",
    "        for i in range(1, n-1):\n",
    "            for j in range(i+1, n):\n",
    "                if dp[0][i-1] and dp[i][j-1] and dp[j][n-1]:\n",
    "                    return True \n",
    "\n",
    "        return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        # 先预计算回文串\n",
    "        n = len(s)\n",
    "        dp = [[True if i == j else False for j in range(n)]for i in range(n)]\n",
    "        for right in range(n):\n",
    "            for left in range(right+1):\n",
    "                if s[left] == s[right] and (right - left <= 2 or dp[left+1][right-1]):\n",
    "                    dp[left][right] = True\n",
    "\n",
    "        # 是否能分割成3份，那么就将字符串分为0:begin,begin+1，mid，mid+1:-1\n",
    "        for begin in range(n-1):\n",
    "            for mid in range(begin, n-1):\n",
    "                if dp[0][begin] and dp[begin+1][mid] and dp[mid+1][-1]:\n",
    "                    return True\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        # dp[i][j] i~j之间字符串是否回文\n",
    "        dp = [[True for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        for j in range(n):\n",
    "            for i in range(j):\n",
    "                dp[i][j] = dp[i+1][j-1] and (s[i] == s[j])\n",
    "        \n",
    "        # i,j 表示中间段的起始位置，1 <= i <= j <= n-2\n",
    "        for i in range(1, n-1):\n",
    "            for j in range(i, n-1):\n",
    "                if dp[0][i-1] and dp[i][j] and dp[j+1][n-1]:\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "\n",
    "\"\"\"\n",
    "------------------------------------------------\n",
    "@Author : Jianhui Luo\n",
    "@FileName : 1745. 分割回文串 IV.py\n",
    "@Time : Created in 10:41 2023/09/08\n",
    "@Motto : 天行健，君子当自强不息。\n",
    "@Description :\n",
    "给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。\n",
    "\n",
    "当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。\n",
    "--------------------------------------------------\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def is_pari(self, s):\n",
    "        n = len(s)\n",
    "        pari_dp = [[False for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        for right in range(n):\n",
    "            for left in range(right + 1):  # 表示一个字符也要取\n",
    "                if s[left] == s[right] and (right - left <= 2 or pari_dp[left + 1][right - 1]):\n",
    "                    pari_dp[left][right] = True\n",
    "\n",
    "        return pari_dp\n",
    "\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        pari_dp = self.is_pari(s)\n",
    "\n",
    "        # 然后将字符串氛围begin，mid，n-1三个区域\n",
    "        n = len(s)\n",
    "        for begin in range(0,n-1):\n",
    "            for mid in range(begin, n-1):\n",
    "                if pari_dp[0][begin] and pari_dp[begin+1][mid] and pari_dp[mid+1][n-1]:\n",
    "                    return True\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        dp1 = [[False for _ in range(len(s)+1)] for _ in range(len(s)+1)]\n",
    "        # for l in range(1, len(s)+1):\n",
    "        for l in range(len(s), 0, -1):\n",
    "            for r in range(l, len(s)+1):\n",
    "                if l == r:\n",
    "                    dp1[l][r] = True\n",
    "                elif l+1 == r:\n",
    "                    if s[l-1] == s[r-1]:\n",
    "                        dp1[l][r] = True\n",
    "                    else:\n",
    "                        dp1[l][r] = False\n",
    "                elif r-l >= 2:\n",
    "                    if s[l-1] == s[r-1] and dp1[l+1][r-1]:\n",
    "                        dp1[l][r] = True\n",
    "        # print(dp1)\n",
    "        for i in range(1, len(s)+1):\n",
    "            for j in range(i+1, len(s)):\n",
    "                s1 = s[0:i]\n",
    "                s2 = s[i:j]\n",
    "                s3 = s[j:len(s)]\n",
    "                # print(str(i)+' '+str(j))\n",
    "                if dp1[1][i] and dp1[i+1][j] and dp1[j+1][len(s)]:\n",
    "                    return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        # 先预计算回文串\n",
    "        n = len(s)\n",
    "        dp = [[True if i == j else False for j in range(n)]for i in range(n)]\n",
    "        for right in range(n):\n",
    "            for left in range(right+1):\n",
    "                if s[left] == s[right] and (right - left <= 2 or dp[left+1][right-1]):\n",
    "                    dp[left][right] = True\n",
    "\n",
    "        # 是否能分割成3份，那么就将字符串分为0:begin,begin+1，mid，mid+1:-1\n",
    "        for begin in range(n-1):\n",
    "            for mid in range(begin,n-1):\n",
    "                if dp[0][begin] and dp[begin+1][mid] and dp[mid+1][-1]:\n",
    "                    return True\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubStr(self, s: str, i, j) -> bool:\n",
    "        while i < j:\n",
    "            if s[i] != s[j]:\n",
    "                return False\n",
    "            i, j = i+1, j-1\n",
    "        return True\n",
    "\n",
    "    def dfs(self, s: str, i, j, left_num, matrix) -> bool:\n",
    "        if left_num == 0:\n",
    "            return matrix[i][j]\n",
    "        \n",
    "        for split in range(i, j):\n",
    "            if matrix[i][split] and self.dfs(s, split+1, j, left_num-1, matrix):\n",
    "                return True\n",
    "        return False\n",
    "        \n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        N = len(s)\n",
    "        matrix = [[True for _ in range(N)] for _ in range(N)]\n",
    "        for i in range(N):\n",
    "            matrix[i][i] = True\n",
    "\n",
    "        for to_add in range(1, len(s)):\n",
    "            for i in range(N - to_add):\n",
    "                start, end = i, i + to_add\n",
    "                matrix[start][end] = matrix[start+1][end-1] and s[start] == s[end]\n",
    "        \n",
    "        return self.dfs(s, 0, N-1, 2, matrix)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        dp = [[True for __ in range(len(s))] for __ in range(len(s))]\n",
    "        for i in range(len(s)-1, -1, -1):\n",
    "            for j in range(i+1, len(s)):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i+1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = False\n",
    "        return any([dp[0][i-1] and dp[i][j] and dp[j+1][-1] for i in range(1, len(s)) for j in range(i, len(s)-1)])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        dp = [[True for __ in range(len(s))] for __ in range(len(s))]\n",
    "        for i in range(len(s)-1, -1, -1):\n",
    "            for j in range(i+1, len(s)):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i+1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = False\n",
    "        return any([dp[0][i-1] and dp[i][j] and dp[j+1][-1] for i in range(1, len(s)) for j in range(i, len(s)-1)])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        dp = [[True for __ in range(len(s))] for __ in range(len(s))]\n",
    "        for i in range(len(s)-1, -1, -1):\n",
    "            for j in range(i+1, len(s)):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i+1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = False\n",
    "        return any([dp[0][i-1] and dp[i][j] and dp[j+1][-1] for i in range(1, len(s)) for j in range(i, len(s)-1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        isok=[[False]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            isok[i][i]=True\n",
    "            l=i-1\n",
    "            r=i+1\n",
    "            while l>=0 and r<n:\n",
    "                if isok[l+1][r-1] and s[l]==s[r]:\n",
    "                    isok[l][r]=True\n",
    "                l-=1\n",
    "                r+=1\n",
    "        for i in range(n-1):\n",
    "            l=i\n",
    "            r=i+1\n",
    "            isok[r][l]=True\n",
    "            while l>=0 and r<n:\n",
    "                if isok[l+1][r-1] and s[l]==s[r]:\n",
    "                    isok[l][r]=True\n",
    "                l-=1\n",
    "                r+=1\n",
    "        @cache\n",
    "        def dfs(i, c):\n",
    "            if c == 2:\n",
    "                return i<=n-1 and isok[i][n-1]\n",
    "            for j in range(i, n - 1):\n",
    "                if isok[i][j]:\n",
    "                    if dfs(j + 1, c + 1):\n",
    "                        return True\n",
    "            return False\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "       @cache\n",
    "       def dfs(i: int, j: int) -> bool:\n",
    "          if i == n or j == 0:\n",
    "             return i == n and j == 0\n",
    "          res = False\n",
    "          for k in range(i, n):\n",
    "             if arr[i][k]:\n",
    "                res = res or dfs(k + 1, j - 1)\n",
    "          return res\n",
    "\n",
    "       n = len(s)\n",
    "       arr = [[False] * n for _ in range(n)]\n",
    "       for i in range(n - 1, -1, -1):\n",
    "          for j in range(i, n):\n",
    "             if i == j or j - i == 1 and s[i] == s[j] or j - i > 1 and s[i] == s[j] and arr[i + 1][j - 1]:\n",
    "                arr[i][j] = True\n",
    "       return dfs(0, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "       @cache\n",
    "       def dfs(i: int, j: int) -> bool:\n",
    "          if i == n or j == 0:\n",
    "             return i == n and j == 0\n",
    "          for k in range(i, n):\n",
    "             if arr[i][k] and dfs(k + 1, j - 1):\n",
    "                return True\n",
    "          return False\n",
    "\n",
    "       n = len(s)\n",
    "       arr = [[False] * n for _ in range(n)]\n",
    "       for i in range(n - 1, -1, -1):\n",
    "          for j in range(i, n):\n",
    "             if i == j or j - i == 1 and s[i] == s[j] or j - i > 1 and s[i] == s[j] and arr[i + 1][j - 1]:\n",
    "                arr[i][j] = True\n",
    "       return dfs(0, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        \n",
    "        n =len(s)  \n",
    "\n",
    "        f = [[0]*n for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            f[i][i]=1\n",
    "        for i in range(n-1):\n",
    "            if s[i]==s[i+1]: \n",
    "                f[i][i+1]=1\n",
    "\n",
    "        for l in range(3,n+1):\n",
    "            for i in range(n-l+1):\n",
    "                j = i+l-1\n",
    "                if s[i]==s[j]: \n",
    "                    f[i][j] = f[i+1][j-1]\n",
    "        @cache\n",
    "        def dfs(i:int,j:int):\n",
    "            if j == 0:\n",
    "                return f[0][i]\n",
    "            ans = 0 \n",
    "            for k in range(j,i+1):\n",
    "                if f[k][i]:\n",
    "                    ans |= dfs(k-1,j-1) \n",
    "            return ans\n",
    "        return bool(dfs(n-1,2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ManacherPlindrome:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def max(a, b):\n",
    "        return a if a > b else b\n",
    "\n",
    "    @staticmethod\n",
    "    def manacher(s):\n",
    "        # 马拉车算法\n",
    "        n = len(s)\n",
    "        arm = [0] * n\n",
    "        left, right = 0, -1\n",
    "        for i in range(0, n):\n",
    "            a, b = arm[left + right - i], right - i + 1\n",
    "            a = a if a < b else b\n",
    "            k = 1 if i > right else a\n",
    "\n",
    "            # 持续增加回文串的长度\n",
    "            while 0 <= i - k and i + k < n and s[i - k] == s[i + k]:\n",
    "                k += 1\n",
    "            arm[i] = k\n",
    "\n",
    "            # 更新右侧最远的回文串边界\n",
    "            k -= 1\n",
    "            if i + k > right:\n",
    "                left = i - k\n",
    "                right = i + k\n",
    "        # 返回每个位置往右的臂长其中 s[i-arm[i]+1: i+arm[i]] 为回文子串范围\n",
    "        # 即以i为中心的最长回文子串长度\n",
    "        return arm\n",
    "\n",
    "    def palindrome(self, s: str) -> (list, list):\n",
    "        # 获取区间的回文串信息\n",
    "        n = len(s)\n",
    "        # 保证所有的回文串为奇数长度，且中心为 # 的为原偶数回文子串，中心为 字母 的为原奇数回文子串\n",
    "        t = \"#\" + \"#\".join(list(s)) + \"#\"\n",
    "        dp = self.manacher(t)\n",
    "        m = len(t)\n",
    "\n",
    "        # 以当前索引作为边界开头的回文子串结束位置索引\n",
    "        start = [[] for _ in range(n)]\n",
    "        # 以当前索引作为边界结尾的回文子串起始位置索引\n",
    "        end = [[] for _ in range(n)]\n",
    "\n",
    "        for j in range(m):\n",
    "            left = j - dp[j] + 1\n",
    "            right = j + dp[j] - 1\n",
    "            while left <= right:\n",
    "                if t[left] != \"#\":\n",
    "                    start[left // 2].append(right // 2)\n",
    "                    end[right//2].append(left//2)\n",
    "                left += 1\n",
    "                right -= 1\n",
    "        return start, end\n",
    "    \n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        start, end = ManacherPlindrome().palindrome(s)\n",
    "        dct = [set(ls) for ls in end]\n",
    "        for i in start[0]:\n",
    "            for j in end[-1]:\n",
    "                if i < j and i+1 in dct[j-1]:\n",
    "                    return True\n",
    "        return False"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
